﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//题目描述：
//给定一个仅包含数字 2 - 9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//
//给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//
//示例 1：
//
//输入：digits = "23"
//输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
//示例 2：
//
//输入：digits = ""
//输出：[]
//示例 3：
//
//输入：digits = "2"
//输出：["a", "b", "c"]

char** ptr;
int ptrTop;
char* temp;
int tempTop;
char str[10][5] = {"\0","\0","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//由于字符2~9对应着相应的几个字符，所以可以用预先用二维数组使2~9作为下标指向它们对应
//的字符，方便遍历

void backtracking(char* digits, int index)
{
    if (digits[index] == '\0') //单层结束条件
    {
        char* p = (char*)malloc(sizeof(char) * (tempTop+1));
        int j;
        for (j = 0; j < tempTop; j++)
        {
            p[j] = temp[j];
        }
        p[j] = '\0';//要将二维数组的每一行都设置'\0',所以p数组要开辟tempTop+1个字节的大小
        ptr[ptrTop++] = p; 
        return;
    }
    int j = 0;
    int i = (int)(digits[index] - 48);//将digits[index]的内容（数字字符）转换成数字，
                                     //该数字作为二维数组的下标
    for (str[i][j]; str[i][j] != '\0'; j++)//单层逻辑循环
    {
        temp[tempTop++] = str[i][j];
        backtracking(digits, index + 1);
        tempTop--;
    }
}
char** letterCombinations(char* digits, int* returnSize) {
    int len = strlen(digits);
    if (len == 0)//特殊情况
    {
        *returnSize = 0;
        return ptr;
    }
    ptr = (char**)malloc(sizeof(char*) * 150);
    temp = (char*)malloc(sizeof(char) * 50);
    int index = 0;
    backtracking(digits, index);
    *returnSize = ptrTop;
    return ptr;
}
int main()
{
    char str[] = "23";
    int sz = 0;
    letterCombinations(str,&sz);
    return 0;
}